(***) ** Les tours de Hanoï - Grand Oral

Les tours de Hanoï sont un jeu de réflexion proposé par le mathématicien français Édouard Lucas dans le tome 3 de ses Récréations mathématiques, parues à titre posthume en 1892.

Le jeu est constitué de trois piques fixées sur un socle et de  `n`  disques de diamètres différents.  Au départ, les  `n`  disques sont empilés sur la première pique dans l'ordre décroissant de leur diamètre, le plus large étant en dessous.

Ce jeu consiste à déplacer les  `n`  disques de la pique 1 à la pique 3 en un minimum de coups, tout en respectant les règles suivantes :

• on ne peut pas déplacer plus d'un disque à la fois ;
  
• on ne peut placer un disque que sur un autre disque de diamètre supérieur ou sur un emplacement vide.
  

Pour tout entier naturel `n`  non nul, on pose `u_n`  le nombre minimal de déplacements nécessaires pour déplacer une tour de  `n`  étages d'une pique à une autre.

1. Déterminer `u_1` , `u_2`  et `u_3` .
2. En observant plus précisément les manipulations nécessaires à la résolution du problème pour `n=3` , donner une relation liant `u_3`  et `u_2` .
3. a. Pour tout entier naturel `n` , exprimer `u_{n+1}`  en fonction de `u_n` .
    b. Démontrer par récurrence que, pour tout entier naturel  `n` , `u_n=2^n-1` .
4. Ci-dessous un extrait du texte original :

En supposant qu'il faut une seconde pour déplacer un disque, estimer le nombre d'années qui devront s'écouler avant que les brahmes ne tombent.